栈和队列

1 栈

1.1 栈的基本概念

1. 栈的定义
   栈(Stack)：只允许在一端进行插入和删除的线性表
   栈顶(Top)：允许进行插入和删除的一端
   栈底(Button):栈底不允许插入和删除
   空栈：不含任何元素的栈
2. 栈的基本操作
   InitStack(&S)
   StackEmpty(S)
   Push(&S,x)
   Pop(&S,&x)
   GetTop(S,&x)
   ClearStack(&S)

1.2 栈的顺序存储结构

1. 顺序栈的实现
   栈的顺序存储称为顺序栈，利用一组连续存储单元存放栈内元素，并设一个栈顶指针。
   描述如下

   #define Maxsize 50            //栈的大小
   typedef struct {
       Elemtype data[Maxsize];
       int top;                 //栈顶指针
   }SqStack;

2. 顺序栈的基本操作
   初始化：

   void InitStack(&S){
       S.top = -1;             //初始化栈顶指针
   }

   判断栈空：

   bool StackEmpty(S){
       if(S.top== -1)          //栈空的标志
           return true;
       else
           return false;
   }

   进栈：

   bool Push(SqStack &S,Elemtype x){
       if(S.top==Maxsize-1)      //栈满的标志
           return false;
       S.top++;                  //指针先加1，在入栈
       S.data[S.top]=x;
       return true;
   
   }

   出栈：

   bool Pop(SqStack &S,Elemtype &x){
       if(S.top==-1)
           return false;
       x = S.data[S.top];
       S.top--;
       return true;
   }

   读栈顶元素

   bool GetTop(SqStack S,Elemtype &x){
       if(S.top==-1)                       //栈空判断
           return false;
       x = S.data[S.top]                   //记录栈顶元素
       return true;
   }

1.3 共享栈
将两个栈的栈底设置为共享空间的两端，两个栈顶向共享空间的中间延伸。

2 队列

2.1 队列的基本概念

1. 队列的定义
   队列是一种操作受限的线性表，只允许在一端进行插入，在另一端进行删除，又称为先进先出的线性表。其中，对首是允许删除的一端，对尾是允许插入的一端。
2. 队列常见的基本操作
   InitQueue(&Q)
   QueueEmpty(Q)
   EnQueue(&Q,x)
   DeQueue(&Q,&x)
   GetHead(Q,&x)

2.2 队列的顺序存储结构

1. 队列的顺序存储
   分配一块连续的存储空间存放队列中的元素，并设两个指针front和rear，front指向对首元素、rear指向队尾元素的下一个位置。
   队列的顺序存储类型描述：

   #define Maxsize 50
   typedef struct{
       Elemtype data[Maxsize];
       int front,rear;
   }SqQueue;

2. 循环队列
   当对首指针front=MaxSize-1 时，再前进一个位置就自动到0，构成循环队列。
   初始： Q.front=Q.rear=0
   对首指针进1：Q.front=(Q.front+1)%MaxSize
   队尾指针进1：Q.rear = (Q.rear+1)%MaxSize
   队列长度：(Q.rear+MaxSize-Q.front)% Maxsize
   在循环队列中为了区分Q.front = q.rear 代表对空还是对满，采用了入队时少用一个队列单元的做法，故：
   队满条件：(Q.rear+1)%MaxSize=q.front
   队空条件:Q.front = Q. rear

3. 循坏队列的操作
   初始化：

   void InitQueue(&Q){
       Q.front = Q.rear = 0;
   }

   判断对空：

   bool isEmpty(Q){
       if(Q.front==Q.rear)
           return true;
       return false;
   }

   入队：

   bool EnQueue(SqQueue &Q,Elemtype x){
       if((Q.rear+1)%Maxsize==Q.front)       //队满则失败
           return false；
       Q.data[Q.rear]=x;
       Q.rear++;
       return true;
   }

   出队：

   bool DeQueue(SqQueue &S,Elemtype &x){
       if(Q.rear==Q.front) return false;          //队空则失败
       x = Q.data[Q.front];
       Q.front = (Q.front+1)%Maxsize;
       return true;
   }

队列的链式存储结构

1. 队列的链式存储
   链队列带有队首指针和队尾指针，其中队首指针指向队首结点，队尾指针指向队尾结点(注意与顺序链表不同)。
   队列的链式存储类型描述：

   typedef struct{
       Elemtype data;
       struct LinkNode *next;
   }LinkNode;
   
   typedef struct {
       LinkNode *front,*rear;
   }LinkQueue;

链式队列通常带头结点。

1. 链式队列的基本操作
   初始化：

   void InitLinkQueue(LinkQueue &Q){
       Q.front = Q.rear =(LinkNode*)malloc(sizeof(LinkNode));
       Q.front = Q.rear = NULL;
   }

   判断队空：

   bool IsEmpty(LinkQueue Q){
       if(Q.front = Q.rear) return true;
       return false;
   }

   入队：

   void EnQueue(LinkQueue &Q,Elemtype x){
       s = (LinkNode*)malloc(sizeof(LinkNode));
       s->data = x;
       s->next = NULL;
       Q.rear->next = s;
       Q.rear = s;
   }

   出队：

   bool DeQueue(LinkQueue &Q,Elemtype &x){
       if(Q.front == Q.rear) return false;
       q = Q.front->next;                //注意头结点
       x = q->data;
       Q.front->next = Q.front->next->next;
       if(Q.rear == p)                 //判断出队后队列为空的情况
           Q.rear = Q.front;
       free(q);
       return true；
   }

2.4 双端队列

双端队列是允许两端都可以进行入队和出队操作的队列。